'''
Created on 2012-8-5

@author: DXD.Spirits
'''


from shortestpath import dijkstra
from containers import DisjointSet


def connected_components(graph):
    '''
    @return: list of connect graphs
    '''
    node_list = [node for node in graph]
    disjointSet = DisjointSet(node_list)
    for dep, edges in graph.iteritems():
        for arr in edges:
            disjointSet.union(dep, arr)
    node_sets = disjointSet.to_sets()
    composants = []
    for nodes in node_sets.values():
        composants.append({node:graph[node] for node in nodes})
    return composants


def mst(graph):
    ''' minimal spanning tree on the undirected graph(V,E)
        @return: a subset of E
    '''
    arc_list = []
    for dep, arcs in graph.iteritems():
        for arr, cost in arcs.iteritems():
            arc_list.append((dep, arr, cost))
    arc_list = sorted(arc_list, key = lambda x : x[2])
    disjointSet = DisjointSet([node for node in graph])
    tree = []
    for arc in arc_list:
        dep, arr, cost = arc
        if disjointSet.find_root(dep) != disjointSet.find_root(arr):
            tree.append(arc)
            disjointSet.union(dep, arr)
    return tree


def steiner(graph, node_subset):
    ''' Steiner(G, F), G=(V, E), F a subset of V
        a minimal subset of E liking all the nodes from F
        NPC but there is a simple algorithm:
            precompute all the node-to-node shortest paths
            link all the nodes in F by these |F|*|F| paths
            than execute a MST on the graph
        with a optimal guarantee <= 2
        we dont care too much about the approximite, why ???
        @return: a subset of E
    '''
    
    node_subset = set(node_subset)
    highway_arcs = []
    for dep in node_subset:
        for arr in node_subset:
            if dep != arr:
                path, cost = dijkstra(graph, dep, arr)
                if len(path) > 1 and set(path[1:-1]).isdisjoint(node_subset):
                    highway_arcs.append((dep, arr, cost))
    return highway_arcs

